package com.erp.framework.util;

import com.erp.framework.SimpleConstants;

/**
 * A class that contains several sorting routines, implemented as static methods. Arrays are rearranged with smallest item first,
 * using compareTo.
 */
public class SortUtil implements SimpleConstants{

    /**
     * Simple insertion sort.
     * 
     * @param a
     *            an array of Comparable items.
     */
    public static void insertionSort(Comparable[] a) {
        int j;

        for (int p = 1; p < a.length; p++) {
            /* 2 */Comparable tmp = a[p];
            /* 3 */for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--)
                /* 4 */a[j] = a[j - 1];
            /* 5 */a[j] = tmp;
        }
    }

    /**
     * Shellsort, using Shell's (poor) increments.
     * 
     * @param a
     *            an array of Comparable items.
     */
    public static void shellsort(Comparable[] a) {
        int j;

        /* 1 */for (int gap = a.length / 2; gap > 0; gap /= 2)
            for (int i = gap; i < a.length; i++) {
                /* 3 */Comparable tmp = a[i];
                /* 4 */for (j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap)
                    /* 5 */a[j] = a[j - gap];
                /* 6 */a[j] = tmp;
            }
    }

    /**
     * Standard heapsort.
     * 
     * @param a
     *            an array of Comparable items.
     */
    public static void heapsort(Comparable[] a) {
        for (int i = a.length / 2; i >= 0; i--)
            /* buildHeap */
            percDown(a, i, a.length);
        for (int i = a.length - 1; i > 0; i--) {
            swapReferences(a, 0, i); /* deleteMax */
            percDown(a, 0, i);
        }
    }

    /**
     * Internal method for heapsort.
     * 
     * @param i
     *            the index of an item in the heap.
     * @return the index of the left child.
     */
    private static int leftChild(int i) {
        return 2 * i + 1;
    }

    /**
     * Internal method for heapsort that is used in deleteMax and buildHeap.
     * 
     * @param a
     *            an array of Comparable items.
     * @index i the position from which to percolate down.
     * @int n the logical size of the binary heap.
     */
    private static void percDown(Comparable[] a, int i, int n) {
        int child;
        Comparable tmp;

        for (tmp = a[i]; leftChild(i) < n; i = child) {
            child = leftChild(i);
            if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0)
                child++;
            if (tmp.compareTo(a[child]) < 0)
                a[i] = a[child];
            else
                break;
        }
        a[i] = tmp;
    }

    /**
     * Mergesort algorithm.
     * 
     * @param a
     *            an array of Comparable items.
     */
    public static void mergeSort(Comparable[] a) {
        Comparable[] tmpArray = new Comparable[a.length];

        mergeSort(a, tmpArray, 0, a.length - 1);
    }

    /**
     * Internal method that makes recursive calls.
     * 
     * @param a
     *            an array of Comparable items.
     * @param tmpArray
     *            an array to place the merged result.
     * @param left
     *            the left-most index of the subarray.
     * @param right
     *            the right-most index of the subarray.
     */
    private static void mergeSort(Comparable[] a, Comparable[] tmpArray, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(a, tmpArray, left, center);
            mergeSort(a, tmpArray, center + 1, right);
            merge(a, tmpArray, left, center + 1, right);
        }
    }

    /**
     * Internal method that merges two sorted halves of a subarray.
     * 
     * @param a
     *            an array of Comparable items.
     * @param tmpArray
     *            an array to place the merged result.
     * @param leftPos
     *            the left-most index of the subarray.
     * @param rightPos
     *            the index of the start of the second half.
     * @param rightEnd
     *            the right-most index of the subarray.
     */
    private static void merge(Comparable[] a, Comparable[] tmpArray, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        // Main loop
        while (leftPos <= leftEnd && rightPos <= rightEnd)
            if (a[leftPos].compareTo(a[rightPos]) <= 0)
                tmpArray[tmpPos++] = a[leftPos++];
            else
                tmpArray[tmpPos++] = a[rightPos++];

        while (leftPos <= leftEnd)
            // Copy rest of first half
            tmpArray[tmpPos++] = a[leftPos++];

        while (rightPos <= rightEnd)
            // Copy rest of right half
            tmpArray[tmpPos++] = a[rightPos++];

        // Copy tmpArray back
        for (int i = 0; i < numElements; i++, rightEnd--)
            a[rightEnd] = tmpArray[rightEnd];
    }

    /**
     * Quicksort algorithm.
     * 
     * @param a
     *            an array of Comparable items.
     */
    public static void quicksort(Comparable[] a) {
        quicksort(a, 0, a.length - 1);
    }

    private static final int CUTOFF = 3;

    /**
     * Method to swap to elements in an array.
     * 
     * @param a
     *            an array of Comparable items.
     * @param index1
     *            the index of the first object.
     * @param index2
     *            the index of the second object.
     */
    public static final void swapReferences(Object[] a, int index1, int index2) {
        Object tmp = a[index1];
        a[index1] = a[index2];
        a[index2] = tmp;
    }

    /**
     * Return median of left, center, and right. Order these and hide the pivot.
     */
    private static Comparable median3(Comparable[] a, int left, int right) {
        int center = (left + right) / 2;
        if (a[center].compareTo(a[left]) < 0)
            swapReferences(a, left, center);
        if (a[right].compareTo(a[left]) < 0)
            swapReferences(a, left, right);
        if (a[right].compareTo(a[center]) < 0)
            swapReferences(a, center, right);

        // Place pivot at position right - 1
        swapReferences(a, center, right - 1);
        return a[right - 1];
    }

    /**
     * Internal quicksort method that makes recursive calls. Uses median-of-three partitioning and a cutoff of 10.
     * 
     * @param a
     *            an array of Comparable items.
     * @param left
     *            the left-most index of the subarray.
     * @param right
     *            the right-most index of the subarray.
     */
    private static void quicksort(Comparable[] a, int left, int right) {
        if (left + CUTOFF <= right) {
            Comparable pivot = median3(a, left, right);

            // Begin partitioning
            int i = left, j = right - 1;
            for (;;) {
                while (a[++i].compareTo(pivot) < 0) {
                }
                while (a[--j].compareTo(pivot) > 0) {
                }
                if (i < j)
                    swapReferences(a, i, j);
                else
                    break;
            }

            swapReferences(a, i, right - 1); // Restore pivot

            quicksort(a, left, i - 1); // Sort small elements
            quicksort(a, i + 1, right); // Sort large elements
        } else
            // Do an insertion sort on the subarray
            insertionSort(a, left, right);
    }

    /**
     * Internal insertion sort routine for subarrays that is used by quicksort.
     * 
     * @param a
     *            an array of Comparable items.
     * @param left
     *            the left-most index of the subarray.
     * @param right
     *            the right-most index of the subarray.
     */
    private static void insertionSort(Comparable[] a, int left, int right) {
        for (int p = left + 1; p <= right; p++) {
            Comparable tmp = a[p];
            int j;

            for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--)
                a[j] = a[j - 1];
            a[j] = tmp;
        }
    }

    /**
     * Quick selection algorithm. Places the kth smallest item in a[k-1].
     * 
     * @param a
     *            an array of Comparable items.
     * @param k
     *            the desired rank (1 is minimum) in the entire array.
     */
    public static void quickSelect(Comparable[] a, int k) {
        quickSelect(a, 0, a.length - 1, k);
    }

    /**
     * Internal selection method that makes recursive calls. Uses median-of-three partitioning and a cutoff of 10. Places the kth
     * smallest item in a[k-1].
     * 
     * @param a
     *            an array of Comparable items.
     * @param left
     *            the left-most index of the subarray.
     * @param right
     *            the right-most index of the subarray.
     * @param k
     *            the desired index (1 is minimum) in the entire array.
     */
    private static void quickSelect(Comparable[] a, int left, int right, int k) {
        if (left + CUTOFF <= right) {
            Comparable pivot = median3(a, left, right);

            // Begin partitioning
            int i = left, j = right - 1;
            for (;;) {
                while (a[++i].compareTo(pivot) < 0) {
                }
                while (a[--j].compareTo(pivot) > 0) {
                }
                if (i < j)
                    swapReferences(a, i, j);
                else
                    break;
            }

            swapReferences(a, i, right - 1); // Restore pivot

            if (k <= i)
                quickSelect(a, left, i - 1, k);
            else if (k > i + 1)
                quickSelect(a, i + 1, right, k);
        } else
            // Do an insertion sort on the subarray
            insertionSort(a, left, right);
    }

    private static final int NUM_ITEMS = 20;
    private static int theSeed = 1;

    private static void checkSort(Integer[] a) {
        for (int i = 0; i < a.length; i++) {
            if (a[i].intValue() != i) {
                System.out.println("Error at " + i);
            }
        }
        // System.out.println( "Finished checksort" );
    }

//    public static void main(String[] args) {
//        System.out.println("***** Integer with Insertion Sort *****");
//        Integer[] a = new Integer[NUM_ITEMS];
//        System.out.println("a: BEFORE SORT");
//        for (int i = 0; i < a.length; i++) {
//            a[i] = new Integer((int) Math.round(Math.random() * i * 1000));
//            System.out.println(i + "=" + a[i]);
//        }
//        SortUtil.insertionSort(a);
//        System.out.println("a: AFTER INSERTION SORT");
//        for (int i = 0; i < a.length; i++) {
//            System.out.println(i + "=" + a[i]);
//        }
//
//        System.out.println("***** Double with Heap Sort *****");
//        Double[] b = new Double[NUM_ITEMS];
//        System.out.println("b: BEFORE SORT");
//        for (int i = 0; i < b.length; i++) {
//            b[i] = new Double(Math.random() * i * 1000);
//            System.out.println(i + "=" + b[i]);
//        }
//        SortUtil.heapsort(b);
//        System.out.println("b: AFTER HEAP SORT");
//        for (int i = 0; i < b.length; i++) {
//            System.out.println(i + "=" + b[i]);
//        }
//
//        /*
//        System.out.println("***** MyInteger(customize) with Shell Sort *****");
//        MyInteger[] c = new MyInteger[NUM_ITEMS];
//        System.out.println("c: BEFORE SORT");
//        for (int i = 0; i < c.length; i++) {
//            c[i] = new MyInteger((int) Math.round(Math.random() * i * 1000));
//            System.out.println(i + "=" + c[i]);
//        }
//        SortUtil.shellsort(c);
//        System.out.println("c: AFTER SHELL SORT");
//        for (int i = 0; i < c.length; i++) {
//            System.out.println(i + "=" + c[i]);
//        }
//        */
//
//        System.out.println("***** String with Merge Sort *****");
//        String[] d = new String[NUM_ITEMS];
//        System.out.println("d: BEFORE SORT");
//        for (int i = 0; i < d.length; i++) {
//            d[i] = new String(String.valueOf(Math.round(Math.random() * i * 1000)));
//            System.out.println(i + "=" + d[i]);
//        }
//        SortUtil.mergeSort(d);
//        System.out.println("d: AFTER MERGE SORT");
//        for (int i = 0; i < d.length; i++) {
//            System.out.println(i + "=" + d[i]);
//        }
//
//        System.out.println("***** BigDecimal with Quick Sort *****");
//        java.math.BigDecimal[] e = new java.math.BigDecimal[NUM_ITEMS];
//        System.out.println("e: BEFORE SORT");
//        for (int i = 0; i < e.length; i++) {
//            e[i] = new java.math.BigDecimal(Math.random() * i * 1000);
//            System.out.println(i + "=" + e[i]);
//        }
//        SortUtil.quicksort(e);
//        System.out.println("e: AFTER QUICK SORT");
//        for (int i = 0; i < e.length; i++) {
//            System.out.println(i + "=" + e[i]);
//        }
//
//        SortUtil.quickSelect(a, NUM_ITEMS / 2);
//
//        /*
//         * for( theSeed = 0; theSeed < 20; theSeed++ ) { SortUtil.insertionSort( a ); //checkSort( a );
//         * 
//         * SortUtil.heapsort( a ); //checkSort( a );
//         * 
//         * SortUtil.shellsort( a ); //checkSort( a );
//         * 
//         * SortUtil.mergeSort( a ); //checkSort( a );
//         * 
//         * SortUtil.quicksort( a ); //checkSort( a );
//         * 
//         * SortUtil.quickSelect( a, NUM_ITEMS / 2 ); //System.out.println( a[ NUM_ITEMS / 2 - 1 ].intValue( ) + " " + // NUM_ITEMS /
//         * 2 ); }
//         */
//    }
}


// sample custom-defined class used for sorting.

//public final class MyInteger implements Comparable, java.io.Serializable {
//    public MyInteger() {
//        this(0);
//    }
//
//    public MyInteger(int x) {
//        value = x;
//    }
//
//    public int intValue() {
//        return value;
//    }
//
//    public String toString() {
//        return Integer.toString(value);
//    }
//
//    public int compareTo(Object rhs) {
//        return value < ((MyInteger) rhs).value ? -1 : value == ((MyInteger) rhs).value ? 0 : 1;
//    }
//
//    public boolean equals(Object rhs) {
//        return rhs != null && value == ((MyInteger) rhs).value;
//    }
//
//    private int value;
//}
